<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>数据结构</title>
<link rel="stylesheet" href="./state/chebian.css">
<link rel="stylesheet" href="./state/nine.css">
<style>
    .zhenwen
    {
        background-color: white;
        width: 60%;
        height: auto;
        margin: auto;
    }
    a:link
    {
        color: black;
        text-decoration: underline;
    }
    a:visited
    {
        color: black;
    }

</style>
</head>

<body>

    <nav class="bodyce">
        <ul class="menus">
            <li class="li">
                <i class="fa fa-th-large" aria-hidden="true"></i>
                线性数据结构
                <ul>
                    <li><a href="#stack">栈</a></li>
                    <li>单调栈</li>
                    <li><a href="#queue">队列</a></li>
                    <li>单调队列</li>
                    <li><a href="#lianb">链表</a></li>
                    <li><a href="#hash">哈希表</a></li>
                    <!-- <li>Toast 轻提示</li> -->
                </ul>
            </li>
            <li class="li">
                <i class="fa fa-check-square" aria-hidden="true"></i>
                树状数据结构
                <ul>
                    <li><a href="#tree">树状数组</a></li>
                    <li>二叉树与平衡树</li>
                    <li>树套树</li>
                    <li>动态树</li>
                    <li>折合树</li>
                    <li>PQ数</li>
                    <li>手指树</li>
                    <li>霍夫曼数</li>
                </ul>
            </li>
            <li class="li">
                <i class="fa fa-comment" aria-hidden="true"></i>
                图
                <ul>
                    <li></li>
                </ul>
            </li>
            <li class="li">
                <i class="fa fa-tags" aria-hidden="true"></i>
                块状数据结构
                <ul>
                    <li>分块思想</li>
                    <li>块状数组</li>
                    <li>块状链表</li>
                    <li>树分块</li>
                    <li>Sqrt Tree</li>

                </ul>
            </li>
            
        </ul>
    </nav>
    <div class="zhenwen">
        <h1>数据结构基础</h1>
        <hr>
        <p class="pd">
            数据结构是计算机科学中的一个核心概念，它涉及计算机存储、组织和管理数据的方式。简而言之，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。这些关系定义了数据元素之间的逻辑或物理布局，以及在这些元素上执行的操作。精心选择和设计的数据结构可以显著提高计算机程序的运行效率和存储效率。</p>
        <p class="pd">数据结构主要关注数据的逻辑结构和物理结构，以及它们之间的相互关系。逻辑结构主要描述数据元素之间的逻辑关系，而不考虑它们在计算机中的物理存储方式。常见的逻辑结构包括线性结构（如数组、链表、栈和队列）和非线性结构（如树、图）。物理结构则关注数据元素在计算机内存中的表示和存储方式，例如顺序存储和链式存储。</p>
        <p class="pd">在数据结构中，我们还需要考虑针对这些数据元素的操作。这些操作可以是基本的访问、插入、删除或修改，也可以是更复杂的算法，如排序和搜索。数据结构的选择将直接影响这些操作的效率。</p>
        <p class="pd">数据结构在计算机科学中具有广泛的应用。例如，在数据库管理系统中，数据结构用于有效地组织和检索大量数据。在图形算法中，图数据结构用于表示和处理复杂的网络关系。在编译器设计中，栈数据结构用于实现函数调用和变量作用域。</p>
        <p class="pd">常见的数据结构包括数组、链表、栈、队列、树和图等。每种数据结构都有其独特的特性和适用场景。例如，数组是一种在内存中连续存储多个元素的结构，具有快速按索引访问和遍历的优点，但添加和删除元素的操作可能较慢。链表则允许在任意位置动态地添加和删除元素，但访问特定元素可能需要遍历整个链表。栈和队列是特殊的线性结构，它们分别遵循后进先出（LIFO）和先进先出（FIFO）的原则，常用于实现函数调用、撤销操作等场景。</p>
        <p class="pd">树和图是非线性结构的代表。树形结构如二叉树、B树等，在查找、排序和索引等方面具有高效性。图结构则用于表示复杂的关系网络，如社交网络、交通网络等。在图算法中，我们可以找到最短路径、检测环、进行网络流分析等。</p>
        <p class="pd">总之，数据结构是计算机科学中的一个基础且重要的概念。它不仅是组织和管理数据的基础，也是设计和实现高效算法的关键。理解和掌握数据结构对于提高编程能力和解决实际问题具有重要意义。</p>
        <br>
        <hr>
        <br>
        <h2>线性数据结构</h2>
        <p class="pd">线性数据结构是一种有序的数据集合，其中元素之间存在一对一的关系。常见的线性数据结构包括数组、链表、栈和队列。这些结构在内存中占用连续或离散的空间，支持高效的插入、删除和查找操作，广泛应用于各种编程场景。</p>
            <br><hr><br>
            <h3  id="stack">栈(stack)</h3><a name="stack"></a>
            <p class="pd">栈是信息学奥林匹克竞赛(以下简称OI)中常用的一种线性数据结构。请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。</p>
            <p><b>STL中的栈</b></p>
            <p class="pd">C++ 中的 STL 也提供了一个容器 <b>std::stack</b>，使用前需要引入 <b>stack</b> 头文件</p>
            <p>定义：stack &lt;datatype &gt; ST;</p>
            <ul>
                <li>元素访问:</li>
                <li>·<b>ST.top();</b>返回栈顶元素</li>
                <li>修改：</li>
                <li>·<b>ST.push(x);</b>插入传入的参数x到栈顶</li>
                <li>·<b>ST.pop();</b>弹出栈顶</li>
                <li>容量：</li>
                <li>·<b>ST.empty();</b>返回栈是否为空</li>
                <li>·<b>ST.size();</b>返回栈中元素的个数</li>
            </ul>
            <p>参考资料：<a class="chankao" href="https://zh.cppreference.com/w/cpp/container/stack"> std::stack - zh.cppreference.com</a></p>
            <br><hr><br>
            <h3 id="queue">队列(queue)</h3><a name="queue"></a>
            <p class="pd">队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。</p>
            <p><b>STL中的队列</b></p>
            <p class="pd">C++ 中的 STL 也提供了一个容器 <b>std::queue</b>，使用前需要引入 <b>queue</b> 头文件</p>
            <p>定义：queue &lt;datatype &gt; QU;</p>
            <ul>
                <li>元素访问:</li>
                <li>·<b>QU.front();</b>返回队首元素</li>
                <li>·<b>QU.back();</b>返回队尾元素</li>
                <li>修改：</li>
                <li>·<b>QU.push(x);</b>插入传入的参数x到队尾</li>
                <li>·<b>QU.pop();</b>弹出队头</li>
                <li>容量：</li>
                <li>·<b>QU.empty();</b>返回队列是否为空</li>
                <li>·<b>QU.size();</b>返回队列中元素的个数</li>
            </ul>
            <h3>特殊队列</h3><br>
            <h4>双端队列</h4>
            <p class="pd">双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 4 个：</p>
            <ul>
                <li>在队首插入一个元素</li>
                <li>在队尾插入一个元素</li>
                <li>在队首删除一个元素</li>
                <li>在队尾删除一个元素</li>
            </ul>
            <p><b>STL中的双端队列</b></p>
            <p class="pd">C++ 中的 STL 也提供了一个容器 <b>std::deque</b>，使用前需要引入 <b>deque</b> 头文件</p>
            <p>定义：deque &lt;datatype &gt; DQ;</p>
            <ul>
                <li>元素访问:</li>
                <li>·<b>DQ.front();</b>返回队首元素</li>
                <li>·<b>DQ.back();</b>返回队尾元素</li>
                <li>修改：</li>
                <li>·<b>DQ.push_back(x);</b>插入传入的参数x到队尾</li>
                <li>·<b>DQ.push_front(x);</b>插入传入的参数x到队头</li>
                <li>·<b>DQ.pop_back();</b>弹出队尾</li>
                <li>·<b>DQ.pop_front();</b>弹出队头</li>
                <li>·<b>DQ.insert();</b>在指定位置前插入元素</li>
                <li>·<b>DQ.erase();</b>删除指定位置的元素</li>
                <li>容量：</li>
                <li>·<b>DQ.empty();</b>返回队列是否为空</li>
                <li>·<b>DQ.size();</b>返回队列中元素的个数</li>
            </ul>
            <p class="pd"><queue> 头文件中还提供了优先队列 std::priority_queue，因其与 堆 更为相似，在此不作过多介绍。</p>
            <h3>循环队列</h3>

            <p class="pd">使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。</p>
            <p class="pd">解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。</p>
            <p>参考资料：</p>
            <ol>
                <li><a href="https://zh.cppreference.com/w/cpp/container/queue">std::queue - zh.cppreference.com</a></li>
                <li><a href="https://zh.cppreference.com/w/cpp/container/deque">std::deque - zh.cppreference.com</a></li>
            </ol>
            <br><hr><br>
            <h3 id="lianb">链表</h3><a name="lianb"></a>
            <p class="pd">链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。</p>
            <h4>与数组的区别</h4>
            <p class="pd">链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：
                链表因其链状的结构，能方便地删除、插入数据，操作次数是 O(1)。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n)。
                数组可以方便地寻找并读取数据，在随机访问中操作次数是 O(1)。但删除、插入的操作次数是 O(n) 次</p>
                <p>C++代码实现：</p>
               <img src="./jpg/链表.jpg" alt="" width="90%">
            <br><hr><br>
            <h3>双向链表</h3>
            <p class="pd">双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。</p>    
                <p>C++代码实现:</p>
               <img src="./state/jpg/双向链表.jpg" alt="" width="90%">
               <br><hr><br>
               <h3>向链表中插入（写入）数据</h3>
               <h3>单向链表</h3>
               <p class="pd">流程大致如下：

                <p class="pd">1.初始化待插入的数据 node；</p>
                <p class="pd">2.将 node 的 next 指针指向 p 的下一个结点；</p>
                <p class="pd">3. 将 p 的 next 指针指向 node。</p> </p>    
                   <p>c++代码实现:</p>
                  <img src="./state/jpg/单向链表.jpg" alt=""width="90%">
               <br><hr><br>
               <h3>单向循环链表</h3>
               <p class="pd">将链表的头尾连接起来，链表就变成了循环链表。由于链表首尾相连，在插入数据时需要判断原链表是否为空：为空则自身循环，不为空则正常插入数据。
                大致流程如下：
                
                <p class="pd">1.初始化待插入的数据 node；</p>
                <p class="pd">2.判断给定链表 p 是否为空；</p>
                <p class="pd">3.若为空，则将 node 的 next 指针和 p 都指向自己；</p>
                <p class="pd">4.否则，将 node 的 next 指针指向 p 的下一个结点；</p>
                <p class="pd">5.将 p 的 next 指针指向 node。</p>  </p> 
                   <p>c++代码实现:</p>
                  <img src="./state/jpg/单向循环链表.jpg" alt=""width="90%">
               <br><hr><br>
            <h3>双向循环链表</h3>
               <p class="pd">在向双向循环链表插入数据时，除了要判断给定链表是否为空外，还要同时修改左、右两个指针。

               大致流程如下：</p>
               
               <p class="pd">1.初始化待插入的数据 node；</p>
               <p class="pd">2.判断给定链表 p 是否为空；</p>
               <p class="pd">3.若为空，则将 node 的 left 和 right 指针，以及 p 都指向自己；</p>
               <p class="pd">4.否则，将 node 的 left 指针指向 p;</p>
               <p class="pd">5.将 node 的 right 指针指向 p 的右结点；</p>
               <p class="pd">6.将 p 右结点的 left 指针指向 node；</p>
               <p class="pd">7.将 p 的 right 指针指向 node。></p>  
                   <p>c++代码实现:</p>
                  <img src="./state/jpg/双向循环链表.jpg" alt=""width="90%">
               <br><hr><br>
               <h3>从链表中删除数据</h3>
               <h3>单向（循环）链表</h3>
               <p>设待删除结点为 p，从链表中删除它时，将 p 的下一个结点 p->next 的值覆盖给 p 即可，与此同时更新 p 的下下个结点。

                流程大致如下：</p>    
                <p>1.将 p 下一个结点的值赋给 p，以抹掉 p->value；</p>
                <p>2..新建一个临时结点 t 存放 p->next 的地址；</p>
                <p>3.将 p 的 next 指针指向 p 的下下个结点，以抹掉 p->next；</p>
                <p>4.删除 t。此时虽然原结点 p 的地址还在使用，删除的是原结点 p->next 的地址，但 p 的数据被 p->next 覆盖，p 名存实亡。</p>
                   <p>c++代码实现:</p>
                  <img src="./state/jpg/单向（循环）链表.jpg" alt=""width="90%">
               <br><hr><br>
               <h3>双向循环链表</h3>
               <p class="pd">流程大致如下：</p>

                <p>1.将 p 左结点的右指针指向 p 的右节点；</p> 
                <p>2.将 p 右结点的左指针指向 p 的左节点；</p> 
                <p>3.新建一个临时结点 t 存放 p 的地址；</p> 
                <p>4.将 p 的右节点地址赋给 p，以避免 p 变成悬垂指针；</p> 
                <p>5.删除 t。</p>    
                   <p>c++代码实现:</p>
                  <img src="./state/jpg/双向（循环）链表.jpg" alt=""width="90%">
               <br><hr><br>
            <h3>异或链表</h3>
            <p class="pd">异或链表（XOR Linked List）本质上还是 双向链表，但它利用按位异或的值，仅使用一个指针的内存大小便可以实现双向链表的功能。</p>
            <p class="pd">我们在结构 Node 中定义 lr = left ^ right，即前后两个元素地址的 按位异或值。正向遍历时用前一个元素的地址异 或当前节点的 lr 可得到后一个元素的地址，反向遍历时用后一个元素的地址异或当前节点的 lr 又可得到前一个的元素地址。 这样一来，便可以用一半的内存实现双向链表同样的功能。</p>

            <h2 id="hash">哈希表</h2><a name="hash"></a>
            <h3>引入</h3>
            <p class="pd">哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。</p>
            <br><hr><br>
            <h3>哈希函数</h3>
            <p class="pd">要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。举个例子，如果键值是一个人的身份证号码，哈希函数就可以是号码的后四位，当然也可以是号码的前四位。生活中常用的「手机尾号」也是一种哈希函数。在实际的应用中，键值可能是更复杂的东西，比如浮点数、字符串、结构体等，这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。</p>
            <p class="pd">能为 key 计算索引之后，我们就可以知道每个键值对应的值 value 应该放在哪里了。假设我们用数组 a 存放数据，哈希函数是 f，那键值对 (key, value) 就应该放在 a[f(key)] 上。不论键值是什么类型，范围有多大，f(key) 都是在可接受范围内的整数，可以作为数组的下标。</p>
            <p class="pd">在 OI 中，最常见的情况应该是键值为整数的情况。当键值的范围比较小的时候，可以直接把键值作为数组的下标，但当键值的范围比较大，比如以 10^9 范围内的整数作为键值的时候，就需要用到哈希表。一般把键值模一个较大的质数作为索引，也就是取 f(x)=x \bmod M 作为哈希函数。</p>
            <p class="pd">另一种比较常见的情况是 key 为字符串的情况，由于不支持以字符串作为数组下标，并且将字符串转化成数字存储也可以避免多次进行字符串比较。所以在 OI 中，一般不直接把字符串作为键值，而是先算出字符串的哈希值，再把其哈希值作为键值插入到哈希表里。关于字符串的哈希值，我们一般采用进制的思想，将字符串想象成一个 127 进制的数。那么，对于每一个长度为 n 的字符串 s，就有：

                x = s_0 \cdot 127^0 + s_1 \cdot 127^1 + s_2 \cdot 127^2 + \dots + s_n \cdot 127^n
                
                我们可以将得到的 x 对 2^{64}（即 unsigned long long 的最大值）取模。这样 unsigned long long 的自然溢出就等价于取模操作了。可以使操作更加方便。</p>
            <p class="pd">这种方法虽然简单，但并不是完美的。可以构造数据使这种方法发生冲突（即两个字符串的 x 对 2^{64} 取模后的结果相同）。</p>
            <p class="pd">我们可以使用双哈希的方法：选取两个大质数 a,b。当且仅当两个字符串的哈希值对 a 和对 b 取模都相等时，我们才认为这两个字符串相等。这样可以大大降低哈希冲突的概率。</p>
            <br><hr><br>
            <h2>冲突</h2>
            <p class="pd">如果对于任意的键值，哈希函数计算出来的索引都不相同，那只用根据索引把 (key, value) 放到对应的位置就行了。但实际上，常常会出现两个不同的键值，他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。在 OI 中，最常用的方法是拉链法。</p>
            <br><hr><br>
            <h2>拉链法</h2>
            <P class="pd">拉链法也称开散列法（open hashing）。

                拉链法是在每个存放数据的地方开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 1\ldots M，哈希表的大小为 N，那么一次插入/查询需要进行期望 
                 
                O(\frac{N}{M}) 次比较。</P>
            <h3>实现</h3>
            <img src="./state/jpg/拉链法1.jpg" alt="" width="90%">
            <p>这里再提供一个封装过的模板，可以像 map 一样用，并且较短</p>
            <img src="./state/jpg/拉链法2.jpg" alt="" width="90%">
            <p class="pd">在这里，hash 函数是针对键值的类型设计的，并且返回一个链表头指针用于查询。在这个模板中我们写了一个键值对类型为 (long long, int) 的 hash 表，并且在查询不存在的键值时返回 -1。函数 hash_map() 用于在定义时初始化。</p>
            <br><hr><br>
            <h2>闭散列法</h2>
            <p class="pd">闭散列方法把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。

                比如线性探查法：如果在 d 处发生冲突，就依次检查 d + 1，d + 2……</p>
            <h3>实现</h3>
            <img src="./state/jpg/闭散列法.jpg" altt="" width="90%">
            <br><hr><br>
            <h1 id="tree">树状数组</h1><a name="tree"></a>
            <h2>引入</h2>
            <p class="pd">树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。</p>
            <p class="pd">普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。</p>

            <p>1.结合律：(x \circ y) \circ z = x \circ (y \circ z)，其中 \circ 是一个二元运算符。
            <p>2.可差分：具有逆运算的运算，即已知 x \circ y 和 x 可以求出 y。</p>
            <p class="pd">需要注意的是：</p>
            <p>1.模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；</p>
            <p>2.例如 \gcd，\max 这些信息不可差分，所以不能用普通树状数组处理，但是：</p>
            <p class="pd">（1）.使用两个树状数组可以用于处理区间最值，见 Efficient Range Minimum Queries using Binary Indexed Trees。</p>
            <p class="pd">（2）.本页面也会介绍一种支持不可差分信息查询的，\Theta(\log^2n) 时间复杂度的拓展树状数组。</p>
            <p class="pd">事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。</p>
            <p class="pd">有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。</p>
            <br><hr><br>
            <h2>树状数组</h2>
            <h3>初步感受</h3>
            <p class="pd">先来举个例子：我们想知道 a[1 \ldots 7] 的前缀和，怎么做？</p>
            <p class="pd">一种做法是：a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7，需要求 7 个数的和。</p>
            <p class="pd">但是如果已知三个数 A，B，C，A = a[1 \ldots 4] 的和，B = a[5 \ldots 6] 的总和，C = a[7 \ldots 7] 的总和（其实就是 a[7] 自己）。你会怎么算？你一定会回答：A + B + C，只需要求 3 个数的和。</p>
            <p class="pd">这就是树状数组能快速求解信息的原因：我们总能将一段前缀 [1, n] 拆成 不多于 \boldsymbol{\log n} 段区间，使得这 \log n 段区间的信息是 已知的。</p>
            <p class="pd">于是，我们只需合并这 \log n 段区间的信息，就可以得到答案。相比于原来直接合并 n 个信息，效率有了很大的提高。</p>
            <p class="pd">不难发现信息必须满足结合律，否则就不能像上面这样合并了。</p>
            <p class="pd">下面这张图展示了树状数组的工作原理：</p>
            <img src="./state/jpg/树状数组工作原理图.jpg" alt="" width="90%">
            <p class="pd">最下面的八个方块代表原始数据数组 a。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组 a 的上级——c 数组。</p>
            <p class="pd">c 数组就是用来储存原始数组 a 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。</p>
            <p class="pd">例如，从图中可以看出：</p>
            <p class="pd">c_2 管辖的是 a[1 \ldots 2]；</p>
            <p class="pd">c_4 管辖的是 a[1 \ldots 4]；</p>
            <p class="pd">c_6 管辖的是 a[5 \ldots 6]；</p>
            <p class="pd">c_8 管辖的是 a[1 \ldots 8]；</p>
            <p class="pd">剩下的 c[x] 管辖的都是 a[x] 自己（可以看做 a[x \ldots x] 的长度为 1 的小区间）。</p>
            <p class="pd">不难发现，c[x] 管辖的一定是一段右边界是 x 的区间总信息。我们先不关心左边界，先来感受一下树状数组是如何查询的。</p>
            <p class="pd">举例：计算 a[1 \ldots 7] 的和。</p>
            <p class="pd">过程：从 c_{7} 开始往前跳，发现 c_{7} 只管辖 a_{7} 这个元素；然后找 c_{6}，发现 c_{6} 管辖的是 a[5 \ldots 6]，然后跳到 c_{4}，发现 c_{4} 管辖的是 a[1 \ldots 4] 这些元素，然后再试图跳到 c_0，但事实上 c_0 不存在，不跳了。</p>
            <p class="pd">我们刚刚找到的 c 是 c_7, c_6, c_4，事实上这就是 a[1 \ldots 7] 拆分出的三个小区间，合并得到答案是 c_7 + c_6 + c_4。</p>
            <p class="pd">举例：计算 a[4 \ldots 7] 的和。</p>
            <p class="pd">我们还是从 c_7 开始跳，跳到 c_6 再跳到 c_4。此时我们发现它管理了 a[1 \ldots 4] 的和，但是我们不想要 a[1 \ldots 3] 这一部分，怎么办呢？很简单，减去 a[1 \ldots 3] 的和就行了。</p>
            <p class="pd">那不妨考虑最开始，就将查询 a[4 \ldots 7] 的和转化为查询 a[1 \ldots 7] 的和，以及查询 a[1 \ldots 3] 的和，最终将两个结果作差。</p>
            <img src="./state/jpg/树状数组计算图.jpg" alt="" width="90%">
            <br><hr><br>
            <h3>管辖区间</h3>
            <p class="pd">那么问题来了，c[x](x \ge 1) 管辖的区间到底往左延伸多少？也就是说，区间长度是多少？</p>
            <p class="pd">树状数组中，规定 c[x] 管辖的区间长度为 2^{k}，其中：</p>
            <p class="pd">1.设二进制最低位为第 0 位，则 k 恰好为 x 二进制表示中，最低位的 1 所在的二进制位数；</p>
            <p class="pd">2.2^k（c[x] 的管辖区间长度）恰好为 x 二进制表示中，最低位的 1 以及后面所有 0 组成的数。</p>
            <p class="pd">举个例子，c_{88} 管辖的是哪个区间？</p>
            <p class="pd">因为 88_{(10)}=01011000_{(2)}，其二进制最低位的 1 以及后面的 0 组成的二进制是 1000，即 8，所以 c_{88} 管辖 8 个 a 数组中的元素。</p>
            <p class="pd">因此，c_{88} 代表 a[81 \ldots 88] 的区间信息。</p>
            <p class="pd">我们记 x 二进制最低位 1 以及后面的 0 组成的数为 \operatorname{lowbit}(x)，那么 c[x] 管辖的区间就是 [x-\operatorname{lowbit}(x)+1, x]。</p>
            <p class="pd">这里注意：\boldsymbol{\operatorname{lowbit}} 指的不是最低位 1 所在的位数 \boldsymbol{k}，而是这个 1 和后面所有 0 组成的 \boldsymbol{2^k}。</p>
            <p class="pd">怎么计算 lowbit？根据位运算知识，可以得到 lowbit(x) = x & -x。</p>
            <h4>lowbit的原理：</h4>
            <p class="pd">将 x 的二进制所有位全部取反，再加 1，就可以得到 -x 的二进制编码。例如，6 的二进制编码是 110，全部取反后得到 001，加 1 得到 010。</p>
            <p class="pd">设原先 x 的二进制编码是 (...)10...00，全部取反后得到 [...]01...11，加 1 后得到 [...]10...00，也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。</p>
            <p class="pd">(...) 和 [...] 中省略号的每一位分别相反，所以 x & -x = (...)10...00 & [...]10...00 = 10...00，得到的结果就是 lowbit。</p>
            <h4>C++代码实现：</h4>
            <img src="./state/jpg/lowbit的原理.jpg" alt="" width="90%">
            <br><hr><br>
            <h3>区间查询</h3>
            <p class="pd">接下来我们来看树状数组具体的操作实现，先来看区间查询。</p>
            <p class="pd">回顾查询 a[4 \ldots 7] 的过程，我们是将它转化为两个子过程：查询 a[1 \ldots 7] 和查询 a[1 \ldots 3] 的和，最终作差。</p>
            <p class="pd">其实任何一个区间查询都可以这么做：查询 a[l \ldots r] 的和，就是 a[1 \ldots r] 的和减去 a[1 \ldots l - 1] 的和，从而把区间问题转化为前缀问题，更方便处理。</p>
            <p class="pd">事实上，将有关 l \ldots r 的区间询问转化为 1 \ldots r 和 1 \ldots l - 1 的前缀询问再差分，在竞赛中是一个非常常用的技巧。</p>
            <p class="pd">那前缀查询怎么做呢？回顾下查询 a[1 \ldots 7] 的过程：从 c_{7} 往前跳，发现 c_{7} 只管辖 a_{7} 这个元素；然后找 c_{6}，发现 c_{6} 管辖的是 a[5 \ldots 6]，然后跳到 c_{4}，发现 c_{4} 管辖的是 a[1 \ldots 4] 这些元素，然后再试图跳到 c_0，但事实上 c_0 不存在，不跳了。
                我们刚刚找到的 c 是 c_7, c_6, c_4，事实上这就是 a[1 \ldots 7] 拆分出的三个小区间，合并一下，答案是 c_7 + c_6 + c_4。</p>
            <p class="pd">观察上面的过程，每次往前跳，一定是跳到现区间的左端点的左一位，作为新区间的右端点，这样才能将前缀不重不漏地拆分。比如现在 c_6 管的是 a[5 \ldots 6]，下一次就跳到 5 - 1 = 4，即访问 c_4。</p>
            <p class="pd">我们可以写出查询 a[1 \ldots x] 的过程：</p>
            <p class="pd">1.从 c[x] 开始往前跳，有 c[x] 管辖 a[x-\operatorname{lowbit}(x)+1 \ldots x]；</p>
            <p class="pd">2.令 x \gets x - \operatorname{lowbit}(x)，如果 x = 0 说明已经跳到尽头了，终止循环；否则回到第一步。</p>
            <p class="pd">3.将跳到的 c 合并。</p>
            <p class="pd">实现时，我们不一定要先把 c 都跳出来然后一起合并，可以边跳边合并。</p>
            <p class="pd">比如我们要维护的信息是和，直接令初始 \mathrm{ans} = 0，然后每跳到一个 c[x] 就 \mathrm{ans} \gets \mathrm{ans} + c[x]，最终 \mathrm{ans} 就是所有合并的结果。</p>
            <h4>C++代码实现：</h4>
            <img src="./state/jpg/区间查询.jpg" alt="" width="90%">
            <br><hr><br>
            <h3>树状数组与其树形态的性质</h3>
            <p class="pd">在讲解单点修改之前，先讲解树状数组的一些基本性质，以及其树形态来源，这有助于更好理解树状数组的单点修改。</p>
            <p class="pd">我们约定：</p>
            <p class="pd">1.l(x) = x - \operatorname{lowbit}(x) + 1。即，l(x) 是 c[x] 管辖范围的左端点。</p>
            <p class="pd">2.对于任意正整数 x，总能将 x 表示成 s \times 2^{k + 1} + 2^k 的形式，其中 \operatorname{lowbit}(x) = 2^k。</p>
            <p class="pd">3.下面「c[x] 和 c[y] 不交」指 c[x] 的管辖范围和 c[y] 的管辖范围不相交，即 [l(x), x] 和 [l(y), y] 不相交。「c[x] 包含于 c[y]」等表述同理。</p>
            <p class="pd">性质 \boldsymbol{1}：对于 \boldsymbol{x \le y}，要么有 \boldsymbol{c[x]} 和 \boldsymbol{c[y]} 不交，要么有 \boldsymbol{c[x]} 包含于 \boldsymbol{c[y]}。</p>
            <p class="pd">性质 \boldsymbol{2}：在 \boldsymbol{c[x]} 真包含于 \boldsymbol{c[x + \operatorname{lowbit}(x)]}。</p>
            <p class="pd">性质 3：对于任意 \boldsymbol{x < y < x + \operatorname{lowbit}(x)}，有 \boldsymbol{c[x]} 和 \boldsymbol{c[y]} 不交。</p>
            <p class="pd">有了这三条性质的铺垫，我们接下来看树状数组的树形态（请忽略 a 向 c 的连边）。</p>
            <img src="./state/jpg/树状数组与其树形态的性质jpg" alt="" width="90%">
            <p class="pd">事实上，树状数组的树形态是 x 向 x + \operatorname{lowbit}(x) 连边得到的图，其中 x + \operatorname{lowbit}(x) 是 x 的父亲。</p>
            <p class="pd">注意，在考虑树状数组的树形态时，我们不考虑树状数组大小的影响，即我们认为这是一棵无限大的树，方便分析。实际实现时，我们只需用到 x \le n 的 c[x]，其中 n 是原数组长度。</p>
            <p class="pd">这棵树天然满足了很多美好性质，下面列举若干（设 fa[u] 表示 u 的直系父亲）：</p>
            <p class="pd">1.u < fa[u]。</p>
            <p class="pd">2.u 大于任何一个 u 的后代，小于任何一个 u 的祖先。</p>
            <p class="pd">3.点 u 的 \operatorname{lowbit} 严格小于 fa[u] 的 \operatorname{lowbit}。</p>
            <h4>证明：</h4>
            <img src="./state/jpg/证明1.png" alt="" width="90%">
            <p class="pd">点 x 的高度是 \log_2\operatorname{lowbit}(x)，即 x 二进制最低位 1 的位数。</p>
            <h4>高度的定义：</h4>
            <img src="./state/jpg/高度的定义.png" alt="" width="90%">
            <p class="pd">1.c[u] 真包含于 c[fa[u]]（性质 2）。</p>
            <p class="pd">2.c[u] 真包含于 c[v]，其中 v 是 u 的任一祖先（在上一条性质上归纳）。</p>
            <p class="pd">3.c[u] 真包含 c[v]，其中 v 是 u 的任一后代（上面那条性质 u，v 颠倒）。</p>
            <p class="pd">4.对于任意 v' > u，若 v' 不是 u 的祖先，则 c[u] 和 c[v'] 不交。</p>
            <h4>证明：</h4>
            <img src="./state/jpg/证明2.png" alt="" width="90%">
            <p class="pd">1.对于任意 v < u，如果 v 不在 u 的子树上，则 c[u] 和 c[v] 不交（上面那条性质 u，v' 颠倒）。</p>
            <p class="pd">2.对于任意 v > u，当且仅当 v 是 u 的祖先，c[u] 真包含于 c[v]（上面几条性质的总结）。这就是树状数组单点修改的核心原理。</p>
            <p class="pd">3.设 u = s \times 2^{k + 1} + 2^k，则其儿子数量为 k = \log_2\operatorname{lowbit}(u)，编号分别为 u - 2^t(0 \le t < k)。</p>
            <p class="pd">4.举例：假设 k = 3，u 的二进制编号为 ...1000，则 u 有三个儿子，二进制编号分别为 ...0111、...0110、...0100。</p>
            <h4>证明：</h4>
            <img src="./state/jpg/证明3.png" alt="" width="90%">
            <p class="pd">1.u 的所有儿子对应 c 的管辖区间恰好拼接成 [l(u), u - 1]。</p>
            <p class="pd">2.举例：假设 k = 3，u 的二进制编号为 ...1000，则 u 有三个儿子，二进制编号分别为 ...0111、...0110、...0100。</p>
            <p class="pd">3.c[...0100] 表示 a[...0001 ~ ...0100]。</p>
            <p class="pd">4.c[...0110] 表示 a[...0101 ~ ...0110]。</p>
            <p class="pd">5.c[...0111] 表示 a[...0111 ~ ...0111]。</p>
            <p class="pd">6.不难发现上面是三个管辖区间的并集恰好是 a[...0001 ~ ...0111]，即 [l(u), u - 1]</p>
            <h4>证明：</h4>
            <img src="./state/jpg/证明4.png" alt="" width="90%">
            <br><hr><br>
            <h3>单点修改</h3>
            <p class="pd">现在来考虑如何单点修改 a[x]。</p>
            <p class="pd">我们的目标是快速正确地维护 c 数组。为保证效率，我们只需遍历并修改管辖了 a[x] 的所有 c[y]，因为其他的 c 显然没有发生变化。</p>
            <p class="pd">管辖 a[x] 的 c[y] 一定包含 c[x]（根据性质 1），所以 y 在树状数组树形态上是 x 的祖先。因此我们从 x 开始不断跳父亲，直到跳得超过了原数组长度为止。</p>
            <p class="pd">设 n 表示 a 的大小，不难写出单点修改 a[x] 的过程：</p>
            <p class="pd">1.初始令 x' = x。</p>
            <p class="pd">2.修改 c[x']。</p>
            <p class="pd">3.令 x' \gets x' + \operatorname{lowbit}(x')，如果 x' > n 说明已经跳到尽头了，终止循环；否则回到第二步。</p>
            <p class="pd">区间信息和单点修改的种类，共同决定 c[x'] 的修改方式。下面给几个例子：</p>
            <p class="pd">1.若 c[x'] 维护区间和，修改种类是将 a[x] 加上 p，则修改方式则是将所有 c[x'] 也加上 p。</p>
            <p class="pd">2.若 c[x'] 维护区间积，修改种类是将 a[x] 乘上 p，则修改方式则是将所有 c[x'] 也乘上 p。</p>
            <p class="pd">然而，单点修改的自由性使得修改的种类和维护的信息不一定是同种运算，比如，若 c[x'] 维护区间和，修改种类是将 a[x] 赋值为 p，可以考虑转化为将 a[x] 加上 p - a[x]。如果是将 a[x] 乘上 p，就考虑转化为 a[x] 加上 a[x] \times p - a[x]。</p>
            <p class="pd">下面以维护区间和，单点加为例给出实现。</p>
            <img src="./state/jpg/单点修改.jpg" alt="" width="90%">
            <br><hr><br>
            <h3>建树</h3>
            <p class="pd">也就是根据最开始给出的序列，将树状数组建出来（c 全部预处理好）。</p>
            <p class="pd">一般可以直接转化为 n 次单点修改，时间复杂度 \Theta(n \log n)（复杂度分析在后面）。</p>
            <p class="pd">比如给定序列 a = (5, 1, 4) 要求建树，直接看作对 a[1] 单点加 5，对 a[2] 单点加 1，对 a[3] 单点加 4 即可。</p>
            <br><hr><br>
            <h3>复杂度分析</h3>
            <p class="pd">空间复杂度显然 \Theta(n)。</p>
            <p class="pd">时间复杂度：</p>
            <p class="pd">1.对于区间查询操作：整个 x \gets x - \operatorname{lowbit}(x) 的迭代过程，可看做将 x 二进制中的所有 1，从低位到高位逐渐改成 0 的过程，拆分出的区间数等于 x 二进制中 1 的数量（即 \operatorname{popcount}(x)）。因此，单次查询时间复杂度是 \Theta(\log n)；</p>
            <p class="pd">2.对于单点修改操作：跳父亲时，访问到的高度一直严格增加，且始终有 x \le n。由于点 x 的高度是 \log_2\operatorname{lowbit}(x)，所以跳到的高度不会超过 \log_2n，所以访问到的 c 的数量是 \log n 级别。因此，单次单点修改复杂度是 \Theta(\log n)。</p>
            <br><hr><br>
            <h2>区间加区间和</h2>
            <p class="pd">该问题可以使用两个树状数组维护差分数组解决。</p>
            <p class="pd">考虑序列 a 的差分数组 d，其中 d[i] = a[i] - a[i - 1]。由于差分数组的前缀和就是原数组，所以 a_i=\sum_{j=1}^i d_j。</p>
            <p class="pd">一样地，我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询 a[1 \ldots r] 的和，即 
                \sum_{i=1}^{r} a_i，进行推导：</p>
            <img src="./state/jpg/推导1.png"alt="" width="90%">
            <p class="pd">观察这个式子，不难发现每个 d_j 总共被加了 r - j + 1 次。接着推导：</p>
            <img src="./state/jpg/推导2.png"alt="" width="90%">
            <p class="pd">
                \sum_{i=1}^r d_i 并不能推出 
                \sum_{i=1}^r d_i \times i 的值，所以要用两个树状数组分别维护 d_i 和 d_i \times i 的和信息。
                
                那么怎么做区间加呢？考虑给原数组 a[l \ldots r] 区间加 x 给 d 带来的影响。</p>
            <p class="pd">因为差分是 d[i] = a[i] - a[i - 1]，</p>
            <p class="pd">1.a[l] 多了 v 而 a[l - 1] 不变，所以 d[l] 的值多了 v。</p>
            <p class="pd">2.a[r + 1] 不变而 a[r] 多了 v，所以 d[r + 1] 的值少了 v。</p>
            <p class="pd">3.对于不等于 l 且不等于 r+1 的任意 i，a[i] 和 a[i - 1] 要么都没发生变化，要么都加了 v，a[i] + v - (a[i - 1] + v) 还是 a[i] - a[i - 1]，所以其它的 d[i] 均不变。</p>
            <p class="pd">那就不难想到维护方式了：对于维护 d_i 的树状数组，对 l 单点加 v，r + 1 单点加 -v；对于维护 d_i \times i 的树状数组，对 l 单点加 v \times l，r + 1 单点加 -v \times (r + 1)。</p>
            <p class="pd">而更弱的问题，「区间加求单点值」，只需用树状数组维护一个差分数组 d_i。询问 a[x] 的单点值，直接求 d[1 \ldots x] 的和即可。</p>
            <h4>C++代码实现：</h4>
            <img src="./state/jpg/区间加区间和.jpg"alt="" width="90%">
            <p class="pd">根据这个原理，应该可以实现「区间乘区间积」，「区间异或一个数，求区间异或值」等，只要满足维护的信息和区间操作是同种运算即可，感兴趣的读者可以自己尝试。</p>
            <br><hr><br>
            <h2>二维树状数组</h2>
            <h3>单点修改，子矩阵查询</h3>
            <p class="pd">二维树状数组，也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题。</p>
            <p class="pd">与一维树状数组类似，我们用 c(x, y) 表示 a(x - \operatorname{lowbit}(x) + 1, y - \operatorname{lowbit}(y) + 1) \ldots a(x, y) 的矩阵总信息，即一个以 a(x, y) 为右下角，高 \operatorname{lowbit}(x)，宽 \operatorname{lowbit}(y) 的矩阵的总信息。</p>
            <p class="pd">对于单点修改，设：</p>
            <img src="./state/jpg/单点修改函数.png"alt="" width="90%">
            <p class="pd">即 f(x, i) 为 x 在树状数组树形态上的第 i 级祖先（第 0 级祖先是自己）。</p>
            <p class="pd">则只有 c(f(x, i), f(y, j)) 中的元素管辖 a(x, y)，修改 a(x, y) 时只需修改所有 c(f(x, i), f(y, j))，其中 f(x, i) \le n，f(y, j) \le m。</p>
            <h4>正确性证明:</h4>
            <img src="./state/jpg/正确性证明1.png"alt="" width="90%">
            <p class="pd">对于查询，我们设：</p>
            <img src="./state/jpg/查询函数.png"alt="" width="90%">
            <p class="pd">则合并所有 c(g(x, i), g(y, j))，其中 g(x, i), g(y, j) > 0。</p>
            <h4>正确性证明:</h4>
            <img src="./state/jpg/正确性证明2.png"alt="" width="90%">
            <p class="pd">下面给出单点加、查询子矩阵和的代码。</p>
            <img src="./state/jpg/单点加代码.jpg"alt="" width="90%">
            <br><hr><br>
            <h3>子矩阵加，求子矩阵和</h3>
            <p class="pd">和一维树状数组的「区间加区间和」问题类似，考虑维护差分数组。</p>
            <p class="pd">二维数组上的差分数组是这样的：</p>
            <img src="./state/jpg/差分数组.png"alt="" width="90%">
            <p class="pd">这样以来，对左上角 (x_1, y_1)，右下角 (x_2, y_2) 的子矩阵区间加 v，相当于在差分数组上，对 d(x_1, y_1) 和 d(x_2 + 1, y_2 + 1) 分别单点加 v，对 d(x_2 + 1, y_1) 和 d(x_1, y_2 + 1) 分别单点加 -v。</p>
            <p class="pd">至于原因，把这四个 d 分别用定义式表示出来，分析一下每项的变化即可。</p>
            <p class="pd">举个例子吧，初始差分数组为 0，给 a(2, 2) \ldots a(3, 4) 子矩阵加 v 后差分数组会变为：</p>
            <img src="./state/jpg/子矩阵.png"alt="" width="90%">
            <p class="pd">（其中 a(2, 2) \ldots a(3, 4) 这个子矩阵恰好是上面位于中心的 2 \times 3 大小的矩阵。）</p>
            <p class="pd">因此，子矩阵加的做法是：转化为差分数组上的四个单点加操作。</p>
            <p class="pd">现在考虑查询子矩阵和：</p>
            <p class="pd">对于点 (x, y)，它的二维前缀和可以表示为：</p>
            <img src="./state/jpg/二维前缀和.png"alt="" width="90%">
            <p class="pd">原因就是差分的前缀和的前缀和就是原本的前缀和。</p>
            <p class="pd">和一维树状数组的「区间加区间和」问题类似，统计 d(h, k) 的出现次数，为 (x - h + 1) \times (y - k + 1)。</p>
            <p class="pd">然后接着推导：</p>
            <img src="./state/jpg/二维推导.png"alt="" width="90%">
            <p class="pd">所以我们需维护四个树状数组，分别维护 d(i, j)，d(i, j) \times i，d(i, j) \times j，d(i, j) \times i \times j 的和信息。
                当然了，和一维同理，如果只需要子矩阵加求单点值，维护一个差分数组然后询问前缀和就足够了。</p>
            <p class="pd">下面给出代码：</p>
            <img src="./state/jpg/子矩阵代码.jpg"alt="" width="90%">
            <br><hr><br>
            <h2>权值树状数组及应用</h2>
            <p class="pd">我们知道，普通树状数组直接在原序列的基础上构建，c_6 表示的就是 a[5 \ldots 6] 的区间信息。</p>
            <p class="pd">然而事实上，我们还可以在原序列的权值数组上构建树状数组，这就是权值树状数组。</p>
            <img src="./state/jpg/权值数组.png"alt="" width="90%">
            <p class="pd">运用权值树状数组，我们可以解决一些经典问题。</p>
            <br><hr><br>
            <h3>单点修改，查询全局第 k 小</h3>
            <p class="pd">在此处只讨论第 k 小，第 k 大问题可以通过简单计算转化为第 k 小问题。</p>
            <p class="pd">该问题可离散化，如果原序列 a 值域过大，离散化后再建立权值数组 b。注意，还要把单点修改中的涉及到的值也一起离散化，不能只离散化原数组 a 中的元素。</p>
            <p class="pd">对于单点修改，只需将对原数列的单点修改转化为对权值数组的单点修改即可。具体来说，原数组 a[x] 从 y 修改为 z，转化为对权值数组 b 的单点修改就是 b[y] 单点减 1，b[z] 单点加 1。</p>
            <p class="pd">对于查询第 k 小，考虑二分 x，查询权值数组中 [1, x] 的前缀和，找到 x_0 使得 [1, x_0] 的前缀和 < k 而 [1, x_0 + 1] 的前缀和 \ge k，则第 k 大的数是 x_0 + 1（注：这里认为 [1, 0] 的前缀和是 0）。</p>
            <p class="pd">这样做时间复杂度是 \Theta(\log^2n) 的。</p>
            <p class="pd">考虑用倍增替代二分。</p>
            <p class="pd">设 x = 0，\mathrm{sum} = 0，枚举 i 从 \log_2n 降为 0：</p>
            <p class="pd">1.查询权值数组中 [x + 1 \ldots x + 2^i] 的区间和 t。</p>
            <p class="pd">2.如果 \mathrm{sum} + t < k，扩展成功，x \gets x + 2^i，\mathrm{sum} \gets \mathrm{sum} + t；否则扩展失败，不操作。</p>
            <p class="pd">这样得到的 x 是满足 [1 \ldots x] 前缀和 < k 的最大值，所以最终 x + 1 就是答案。</p>
            <p class="pd">看起来这种方法时间效率没有任何改善，但事实上，查询 [x + 1 \ldots x + 2^i] 的区间和只需访问 c[x + 2^i] 的值即可。</p>
            <p class="pd">原因很简单，考虑 \operatorname{lowbit}(x + 2^i)，它一定是 2^i，因为 x 之前只累加过 2^j 满足 j > i。因此 c[x + 2^i] 表示的区间就是 [x + 1 \ldots x + 2^i]。</p>
            <p class="pd">如此一来，时间复杂度降低为 \Theta(\log n)。</p>
            <h4>C++代码实现：</h4>
            <img src="./state/jpg/查询全局第k小.jpg"alt="" width="90%">
            <br><hr><br>
            <h3>全局逆序对（全局二维偏序）</h3>
            <p class="pd">全局逆序对也可以用权值树状数组巧妙解决。问题是这样的：给定长度为 n 的序列 a，求 a 中满足 i < j 且 a[i] > a[j] 的数对 (i, j) 的数量。</p>
            <p class="pd">该问题可离散化，如果原序列 a 值域过大，离散化后再建立权值数组 b。</p>
            <p class="pd">我们考虑从 n 到 1 倒序枚举 i，作为逆序对中第一个元素的索引，然后计算有多少个 j > i 满足 a[j] < a[i]，最后累计答案即可。</p>
            <p class="pd">事实上，我们只需要这样做（设当前 a[i] = x）：</p>
            <p class="pd">1.查询 b[1 \ldots x - 1] 的前缀和，即为左端点为 a[i] 的逆序对数量。</p>
            <p class="pd">2.b[x] 自增 1；</p>
            <p class="pd">原因十分自然：出现在 b[1 \ldots x-1] 中的元素一定比当前的 x = a[i] 小，而 i 的倒序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 j 大于当前遍历到的索引 i。</p>
            <p class="pd">用例子说明，a = (4, 3, 1, 2, 1)。</p>
            <p class="pd">
                i 按照 5 \to 1 扫：</p>
            <p class="pd">1.a[5] = 1，查询 b[1 \ldots 0] 前缀和，为 0，b[1] 自增 1，b = (1, 0, 0, 0)。</p>
            <p class="pd">2.a[4] = 2，查询 b[1 \ldots 1] 前缀和，为 1，b[2] 自增 1，b = (1, 1, 0, 0)。</p>
            <p class="pd">3.a[3] = 1，查询 b[1 \ldots 0] 前缀和，为 0，b[1] 自增 1，b = (2, 1, 0, 0)。</p>
            <p class="pd">4.a[2] = 3，查询 b[1 \ldots 2] 前缀和，为 3，b[3] 自增 1，b = (2, 1, 1, 0)。</p>
            <p class="pd">5.a[1] = 4，查询 b[1 \ldots 3] 前缀和，为 4，b[4] 自增 1，b = (2, 1, 1, 1)。</p>
            <p class="pd">所以最终答案为 0 + 1 + 0 + 3 + 4 = 8。</p>
            <p class="pd">注意到，遍历 i 后的查询 b[1 \ldots x - 1] 和自增 b[x] 的两个步骤可以颠倒，变成先自增 b[x] 再查询 b[1 \ldots x - 1]，不影响答案。两个角度来解释：</p>
            <p class="pd">1.对 b[x] 的修改不影响对 b[1 \ldots x - 1] 的查询。</p>
            <p class="pd">2.颠倒后，实质是在查询 i \le j 且 a[i] > a[j] 的数对数量，而 i = j 时不存在 a[i] > a[j]，所以 i \le j 相当于 i < j，所以这与原来的逆序对问题是等价的。</p>
            <p class="pd">如果查询非严格逆序对（i < j 且 a[i] \ge a[j]）的数量，那就要改为查询 b[1 \ldots x] 的和，这时就不能颠倒两步了，还是两个角度来解释：</p>
            <p class="pd">1.对 b[x] 的修改 影响 对 b[1 \ldots x] 的查询。</p>
            <p class="pd">2.颠倒后，实质是在查询 i \le j 且 a[i] \ge a[j] 的数对数量，而 i = j 时恒有 a[i] \ge a[j]，所以 i \le j 不相当于 i < j，与原问题 不等价。</p>
            <p class="pd">如果查询 i \le j 且 a[i] \ge a[j] 的数对数量，那这两步就需要颠倒了。</p>
            <p class="pd">另外，对于原逆序对问题，还有一种做法是正着枚举 j，查询有多少 i < j 满足 a[i] > a[j]。做法如下（设 x = a[j]）：</p>
            <p class="pd">1.查询 b[x + 1 \ldots V]（V 是 b 的大小，即 a 的值域（或离散化后的值域））的区间和。</p>
            <p class="pd">2.将 b[x] 自增 1。</p>
            <p class="pd">原因：出现在 b[x + 1 \ldots V] 中的元素一定比当前的 x = a[j] 大，而 j 的正序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 i 小于当前遍历到的索引 j。</p>
            <br><hr><br>
            <h2>树状数组维护不可差分信息</h2>
            <p class="pd">注意，这种方法虽然码量小，但单点修改和区间查询的时间复杂度均为 \Theta(\log^2n)，比使用线段树的时间复杂度 \Theta(\log n) 劣。</p>
            <h3>区间查询</h3>
            <p class="pd">我们还是基于之前的思路，从 r 沿着 \operatorname{lowbit} 一直向前跳，但是我们不能跳到 l 的左边。</p>
            <p class="pd">因此，如果我们跳到了 c[x]，先判断下一次要跳到的 x - \operatorname{lowbit}(x) 是否小于 l：</p>
            <p class="pd">1.如果小于 l，我们直接把 \boldsymbol{a[x]} 单点 合并到总信息里，然后跳到 c[x - 1]。</p>
            <p class="pd">2.如果大于等于 l，说明没越界，正常合并 c[x]，然后跳到 c[x - \operatorname{lowbit}(x)] 即可。</p>
            <p class="pd">下面以查询区间最大值为例，给出代码：</p>
            <img src="./state/jpg/查询区间最大值.jpg"alt="" width="90%">
            <p class="pd">可以证明，上述算法的时间复杂度是 \Theta(\log^2n)。</p>
            <h4>时间复杂度证明：</h4>
            <img src="./state/jpg/时间复杂度证明.png"alt="" width="90%">
            <br><hr><br>
            <h3>单点更新</h3>
            <p class="pd">更新 a[x] 后，我们只需要更新满足在树状数组树形态上，满足 y 是 x 的祖先的 c[y]。</p>
            <p class="pd">对于最值（以最大值为例），一种常见的错误想法是，如果 a[x] 修改成 p，则将所有 c[y] 更新为 \max(c[y], p)。下面是一个反例：(1, 2, 3, 4, 5) 中将 5 修改成 4，最大值是 4，但按照上面的修改这样会得到 5。将 c[y] 直接修改为 p 也是错误的，一个反例是，将上面例子中的 3 修改为 4。</p>
            <p class="pd">事实上，对于不可差分信息，不存在通过 p 直接修改 c[y] 的方式。这是因为修改本身就相当于是把旧数从原区间「移除」，然后加入一个新数。「移除」时对区间信息的影响，相当于做「逆运算」，而不可差分信息不存在「逆运算」，所以无法直接修改 c[y]。</p>
            <p class="pd">换句话说，对每个受影响的 c[y]，这个区间的信息我们必定要重构了。</p>
            <p class="pd">考虑 c[y] 的儿子们，它们的信息一定是正确的（因为我们先更新儿子再更新父亲），而这些儿子又恰好组成了 [l(y), y - 1] 这一段管辖区间，那再合并一个单点 a[y] 就可以合并出 [l(y), y]，也就是 c[y] 了。这样，我们能用至多 \log n 个区间重构合并出每个需要修改的 c。</p>
            <img src="./state/jpg/单点更新.jpg"alt="" width="90%">
            <p class="pd">容易看出上述算法时间复杂度为 \Theta(\log^2n)。</p>
            <br><hr><br>
            <h2>建树</h2>
            <p class="pd">可以考虑拆成 n 个单点修改，\Theta(n\log^2n) 建树。</p>
            <p class="pd">也有 \Theta(n) 的建树方法。</p>

            
            </div>

    <div class="footer no-mp">
        <div class = "lv"></div>
          <div class="foot_link">
              <a href="#">关于我们</a>
              <span>|</span>
              <a href="#">联系我们</a>
              <span>|</span>
              <a href="#">招聘人才</a>
              <span>|</span>
              <a href="#">友情链接</a>		
          </div>
          <p> © 2024 All Rights Reserved</p>
</body>
</html>
